#include "generator-algorithm.h"
#include <gtest/gtest.h>
#include <algorithm>
#include <sstream>
#include "algo-support-reconnect.h"
#include <boost/foreach.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_io.hpp>
#include <fstream>
#include "macros.h"

#define foreach BOOST_FOREACH

namespace cccn 
{

using namespace std;
using namespace boost;

////////////////////////////////
//                            //
// Local functions definition //
//                            //
////////////////////////////////

/**
 * Return an all-zero k-tuple
 */
vector<uint>
FirstSequence (uint k)
  {
  return vector<uint> (k, 0);
  }

/**
 * Increment a k-tuple sequence by 1
 *
 * \param seq a k-tuple sequence
 * \param n all elements of the k-tuple are less than n
 * \return true if seq is set to the next one successfully, or false if seq is the final one
 */
bool
NextSequence (vector<uint>& seq, const uint n)
  {
  vector<uint>::reverse_iterator it = seq.rbegin ();
  while (it != seq.rend ())
    {
    // do increment
    (*it)++;

    // perform ripple carry propagation
    if ((*it) == n)
      {
      (*it)--;
      it++;
      }
    else
      {
      // adjustment after ripple carry is absorted
      for (vector<uint>::reverse_iterator jt=it; jt!=seq.rbegin ();)
        {
        jt--;
        (*jt) = 0;
        }
      return true;
      }
    }
  return false;
  }

/**
 * Return the first combination for a "n choose k" problem
 *
 * \return a vector of k unique numbers, each represents an item chosen
 */
vector<uint> 
FirstCombination (uint k)
  {
  vector<uint> comb;
  for (uint i=0; i<k; i++)
    {
    comb.push_back (i);
    }
  return comb;
  }

/**
 * Return the next combination for an "n choose k" problem
 *
 * \param comb contains k unique numbers (all are less than n), each represents one of the n items chosen. 
 * These numbers are changed to the next combination after the function is called
 * \param n the total number of items
 * \return true if comb is set to the next combination successfully, or false if comb is already the 
 * last combination
 */
bool 
NextCombination (vector<uint>& comb, const uint n)
  {
  vector<uint>::reverse_iterator it = comb.rbegin ();  
  while (it != comb.rend ())
    {
    // do increment
    (*it)++;

    // perform ripple carry propagation
    if (
      (it == comb.rbegin () && (*it) == n) ||
      (it != comb.rbegin () && (*it) == (*(it-1)))
      )
      {
      (*it)--;
      it++;
      }
    else
      {
      // adjustment after ripple carry is absorted
      for (vector<uint>::reverse_iterator jt=it; jt!=comb.rbegin ();)
        {
        jt--;
        (*jt) = (*it) + (it - jt);
        }
      // stop progating ripple carry
      return true;
      }
    }
  return false;
  }

/**
 * Return the first permutation of a "n choose k with order" problem
 *
 * \return a vector of k unique numbers, each represents an item chosen
 */
vector<uint>
FirstPermutation (uint k)
  {
  return FirstCombination (k);
  }

/**
 * Return the next permutation for a "n choose k with order" problem
 *
 * \param perm contain k nuique numbers, each represents an item chosen
 * \param n the total number of available items
 * \return true if a next permutation exists, or false if the given k numbers
 * are already the last permutation
 */
bool
NextPermutation (vector<uint>& perm, const uint n)
  {
  if (next_permutation (perm.begin (), perm.end ()))
    {
    return true;
    }
  else
    {
    if (NextCombination (perm, n))
      {
      return true;
      }
    else
      {
      reverse (perm.begin (), perm.end ());
      return false;
      }
    }
  }
}; // namespace cccn

/////////////
//         //
// TESTING //
//         //
/////////////

using namespace cccn;
using namespace cccn::internal;

::testing::AssertionResult 
VectorIsEqual (const vector<uint>& actual, const uint expect[])
  {
  if (equal (actual.begin (), actual.end (), expect))
    {
    return ::testing::AssertionSuccess ();
    }
  else
    {
    ostringstream ostr;

    ostr << "actual = (" << actual.front ();
    bool isFirst = true;
    foreach (const uint& n, actual)
      {
      if (isFirst)
        {
        isFirst = false;
        continue;
        }
      ostr << "," << n;
      }
    ostr << "), ";
    
    ostr << "but expected = (" << expect[0];
    isFirst = true;
    for (uint i=1; i<actual.size (); i++)
      {
      ostr << "," << expect[i];
      }
    ostr << ")";
    
    return ::testing::AssertionFailure () << ostr.str ();
    }
  }

TEST (FirstCombinationTest, kValueTest)
  {
  uint k3_ans[]  = {0, 1, 2};
  uint k4_ans[]  = {0, 1, 2, 3};
  uint k10_ans[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

  vector<uint> k3 = FirstCombination (3);
  vector<uint> k4 = FirstCombination (4);
  vector<uint> k10 = FirstCombination (10);

  EXPECT_TRUE (VectorIsEqual (k3, k3_ans)); //(equal (k3.begin (), k3.end (), k3_ans));
  EXPECT_TRUE (VectorIsEqual (k4, k4_ans)); //(equal (k4.begin (), k4.end (), k4_ans));
  EXPECT_TRUE (VectorIsEqual (k10, k10_ans)); //(equal (k10.begin (), k10.end (), k10_ans));
  }

TEST (NextCombinationTest, TenChooseOneTest)
  {
  const uint n = 10;
  const uint k = 1;

  uint s1[]  = {0};
  uint s2[]  = {1};
  uint s3[]  = {2};
  uint s4[]  = {3};
  uint s5[]  = {4};
  uint s6[]  = {5};
  uint s7[]  = {6};
  uint s8[]  = {7};
  uint s9[]  = {8};
  uint s10[] = {9};

  vector<uint> combination;

  combination = FirstCombination (k);
  EXPECT_TRUE (VectorIsEqual (combination, s1));

  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s2));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s3));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s4));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s5));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s6));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s7));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s8));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s9));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s10));

  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s10));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s10));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s10));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s10));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s10));

  }

TEST (NextCombinationTest, SixChooseThreeTest)
  {
  const uint n = 6;
  const uint k = 3;

  uint s1[]  = {0, 1, 2};
  uint s2[]  = {0, 1, 3};
  uint s3[]  = {0, 1, 4};
  uint s4[]  = {0, 1, 5};
  uint s5[]  = {0, 2, 3};
  uint s6[]  = {0, 2, 4};
  uint s7[]  = {0, 2, 5};
  uint s8[]  = {0, 3, 4};
  uint s9[]  = {0, 3, 5};
  uint s10[] = {0, 4, 5};
  uint s11[] = {1, 2, 3};
  uint s12[] = {1, 2, 4};
  uint s13[] = {1, 2, 5};
  uint s14[] = {1, 3, 4};
  uint s15[] = {1, 3, 5};
  uint s16[] = {1, 4, 5};
  uint s17[] = {2, 3, 4};
  uint s18[] = {2, 3, 5};
  uint s19[] = {2, 4, 5};
  uint s20[] = {3 ,4, 5};

  vector<uint> combination = FirstCombination (3);
  EXPECT_TRUE (VectorIsEqual (combination, s1));

  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s2));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s3));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s4));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s5));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s6));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s7));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s8));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s9));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s10));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s11));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s12));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s13));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s14));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s15));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s16));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s17));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s18));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s19));
  EXPECT_TRUE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s20));

  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s20));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s20));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s20));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s20));
  EXPECT_FALSE (NextCombination (combination, n));
  EXPECT_TRUE (VectorIsEqual (combination, s20));
  }

TEST (FirstSequenceTest, kValueTest)
  {
  uint k3_ans[]  = {0, 0, 0};
  uint k10_ans[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

  vector<uint> seq = FirstSequence (3);
  EXPECT_TRUE (VectorIsEqual (seq, k3_ans));
  seq = FirstSequence (10);
  EXPECT_TRUE (VectorIsEqual (seq, k10_ans));
  }

TEST (NextSequenceTest, ThreeTupleBaseThreeTest)
  {
  const uint k = 3;
  const uint base = 3;

  uint s1[]  = {0, 0, 0};
  uint s2[]  = {0, 0, 1};
  uint s3[]  = {0, 0, 2};
  uint s4[]  = {0, 1, 0};
  uint s5[]  = {0, 1, 1};
  uint s6[]  = {0, 1, 2};
  uint s7[]  = {0, 2, 0};
  uint s8[]  = {0, 2, 1};
  uint s9[]  = {0, 2, 2};
  uint s10[] = {1, 0, 0};
  uint s11[] = {1, 0, 1};
  uint s12[] = {1, 0, 2};
  uint s13[] = {1, 1, 0};
  uint s14[] = {1, 1, 1};
  uint s15[] = {1, 1, 2};
  uint s16[] = {1, 2, 0};
  uint s17[] = {1, 2, 1};
  uint s18[] = {1, 2, 2};
  uint s19[] = {2, 0, 0};
  uint s20[] = {2, 0, 1};
  uint s21[] = {2, 0, 2};
  uint s22[] = {2, 1, 0};
  uint s23[] = {2, 1, 1};
  uint s24[] = {2, 1, 2};
  uint s25[] = {2, 2, 0};
  uint s26[] = {2, 2, 1};
  uint s27[] = {2, 2, 2};

  vector<uint> seq = FirstSequence (k);
  EXPECT_TRUE (VectorIsEqual (seq, s1));

  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s2));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s3));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s4));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s5));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s6));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s7));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s8));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s9));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s10));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s11));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s12));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s13));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s14));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s15));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s16));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s17));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s18));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s19));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s20));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s21));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s22));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s23));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s24));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s25));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s26));
  EXPECT_TRUE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s27));

  EXPECT_FALSE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s27));
  EXPECT_FALSE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s27));
  EXPECT_FALSE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s27));
  EXPECT_FALSE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s27));
  EXPECT_FALSE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s27));
  EXPECT_FALSE (NextSequence (seq, base));
  EXPECT_TRUE (VectorIsEqual (seq, s27));

  }

TEST (FirstPermutation, kValueTest)
  {
  uint k3[] = {0, 1, 2};
  uint k5[] = {0, 1, 2, 3, 4};

  vector<uint> perm = FirstPermutation (3);
  EXPECT_TRUE (VectorIsEqual (perm, k3));
  perm = FirstPermutation (5);
  EXPECT_TRUE (VectorIsEqual (perm, k5));
  }

TEST (NextPermutationTest, TenChooseOneTest)
  {
  const uint n = 10;
  const uint k = 1;

  uint s1[]  = {0};
  uint s2[]  = {1};
  uint s3[]  = {2};
  uint s4[]  = {3};
  uint s5[]  = {4};
  uint s6[]  = {5};
  uint s7[]  = {6};
  uint s8[]  = {7};
  uint s9[]  = {8};
  uint s10[] = {9};

  vector<uint> perm;

  perm = FirstPermutation (k);
  EXPECT_TRUE (VectorIsEqual (perm, s1));

  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s2));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s3));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s4));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s5));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s6));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s7));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s8));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s9));
  EXPECT_TRUE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s10));

  EXPECT_FALSE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s10));
  EXPECT_FALSE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s10));
  EXPECT_FALSE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s10));
  EXPECT_FALSE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s10));
  EXPECT_FALSE (NextPermutation (perm, n));
  EXPECT_TRUE (VectorIsEqual (perm, s10));

  }

TEST (NextPermutationTest, FourChooseThreeTest)
  {
  const uint n = 4;
  const uint k = 3;

  uint s1[]  = {0,1,2};
  uint s2[]  = {0,2,1};
  uint s3[]  = {1,0,2};
  uint s4[]  = {1,2,0};
  uint s5[]  = {2,0,1};
  uint s6[]  = {2,1,0};
  uint s7[]  = {0,1,3};
  uint s8[]  = {0,3,1};
  uint s9[]  = {1,0,3};
  uint s10[] = {1,3,0};
  uint s11[] = {3,0,1};
  uint s12[] = {3,1,0};
  uint s13[] = {0,2,3};
  uint s14[] = {0,3,2};
  uint s15[] = {2,0,3};
  uint s16[] = {2,3,0};
  uint s17[] = {3,0,2};
  uint s18[] = {3,2,0};
  uint s19[] = {1,2,3};
  uint s20[] = {1,3,2};
  uint s21[] = {2,1,3};
  uint s22[] = {2,3,1};
  uint s23[] = {3,1,2};
  uint s24[] = {3,2,1};

  vector<uint> perm;
  perm = FirstPermutation (3);
  EXPECT_TRUE (VectorIsEqual (perm, s1));

  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s2));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s3));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s4));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s5));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s6));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s7));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s8));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s9));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s10));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s11));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s12));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s13));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s14));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s15));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s16));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s17));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s18));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s19));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s20));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s21));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s22));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s23));
  EXPECT_TRUE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s24));

  EXPECT_FALSE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s24));
  EXPECT_FALSE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s24));
  EXPECT_FALSE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s24));
  EXPECT_FALSE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s24));
  EXPECT_FALSE (NextPermutation (perm, 4));
  EXPECT_TRUE (VectorIsEqual (perm, s24));
  }

TEST (GetPermutationAtTest, FourChooseThreeOrderedTest)
  {
  const uint n = 4;
  const uint r = 3;
  const uint i_max = 24;

  uint s[][3] = {
    {0,1,2},
    {0,1,3},
    {0,2,1},
    {0,2,3},
    {0,3,1},
    {0,3,2},
    {1,0,2},
    {1,0,3},
    {1,2,0},
    {1,2,3},
    {1,3,0},
    {1,3,2},
    {2,0,1},
    {2,0,3},
    {2,1,0},
    {2,1,3},
    {2,3,0},
    {2,3,1},
    {3,0,1},
    {3,0,2},
    {3,1,0},
    {3,1,2},
    {3,2,0},
    {3,2,1}};

  uint dummy[] = {0,0,0};

  vector<uint> perm;
  for (uint i=0; i<i_max+5; i++)
    {
    perm = GetPermutationAt (n, r, i);
    EXPECT_TRUE (VectorIsEqual (perm, s[min(i, i_max-1)])) << "error occurs at i = " << i;
    } 
  }

TEST (GetPermutationAtTest, FiveChooseTwoOrderedTest)
  {
  const uint n = 5;
  const uint r = 2;
  const uint i_max = 20;

  uint s[][2] = {
    {0,1},
    {0,2},
    {0,3},
    {0,4},
    {1,0},
    {1,2},
    {1,3},
    {1,4},
    {2,0},
    {2,1},
    {2,3},
    {2,4},
    {3,0},
    {3,1},
    {3,2},
    {3,4},
    {4,0},
    {4,1},
    {4,2},
    {4,3}
    };

  vector<uint> perm;
  for (uint i=0; i<i_max+5; i++)
    {
    perm = GetPermutationAt (n, r, i);
    EXPECT_TRUE (VectorIsEqual (perm, s[min(i, i_max-1)])) << "error occurs at i = " << i;
    } 
  }

TEST (GetPermutationAtTest, TenChooseOneTest)
  {
  const uint n = 10;
  const uint r = 1;
  const uint i_max = 10;

  uint s[][1] = {
    {0},
    {1},
    {2},
    {3},
    {4},
    {5},
    {6},
    {7},
    {8},
    {9},
    };

  vector<uint> pattern;
  for (uint i=0; i<i_max+10; i++)
    {
    pattern = GetPermutationAt (n, r, i);
    EXPECT_TRUE (VectorIsEqual (pattern, s[min(i, i_max-1)])) << "error at i = " << i;
    }
  }

TEST (GetCombinationAtTest, SixChooseThreeTest)
  {
  const uint n = 6;
  const uint r = 3;
  const uint i_max = 20;

  uint s[][3] = {
    {0,1,2},
    {0,1,3},
    {0,1,4},
    {0,1,5},
    {0,2,3},
    {0,2,4},
    {0,2,5},
    {0,3,4},
    {0,3,5},
    {0,4,5},
    {1,2,3},
    {1,2,4},
    {1,2,5},
    {1,3,4},
    {1,3,5},
    {1,4,5},
    {2,3,4},
    {2,3,5},
    {2,4,5},
    {3,4,5}};

  vector<uint> pattern;
  for (uint i=0; i<i_max+10; i++)
    {
    pattern = GetCombinationAt (n, r, i);
    EXPECT_TRUE (VectorIsEqual (pattern, s[min(i, i_max-1)])) << "error at i = " << i;
    }
  }

TEST (GetCombinationAtTest, SixChooseFourTest)
  {
  const uint n = 6;
  const uint r = 4;
  const uint i_max = 15;

  uint s[][4] = {
    {0,1,2,3},
    {0,1,2,4},
    {0,1,2,5},
    {0,1,3,4},
    {0,1,3,5},
    {0,1,4,5},
    {0,2,3,4},
    {0,2,3,5},
    {0,2,4,5},
    {0,3,4,5},
    {1,2,3,4},
    {1,2,3,5},
    {1,2,4,5},
    {1,3,4,5},
    {2,3,4,5},
    };

  vector<uint> pattern;
  for (uint i=0; i<i_max+10; i++)
    {
    pattern = GetCombinationAt (n, r, i);
    EXPECT_TRUE (VectorIsEqual (pattern, s[min(i, i_max-1)])) << "error at i = " << i;
    }
  }

TEST (GetCombinationAtTest, TenChooseOneTest)
  {
  const uint n = 10;
  const uint r = 1;
  const uint i_max = 10;

  uint s[][1] = {
    {0},
    {1},
    {2},
    {3},
    {4},
    {5},
    {6},
    {7},
    {8},
    {9},
    };

  vector<uint> pattern;
  for (uint i=0; i<i_max+10; i++)
    {
    pattern = GetCombinationAt (n, r, i);
    EXPECT_TRUE (VectorIsEqual (pattern, s[min(i, i_max-1)])) << "error at i = " << i;
    }
  }

TEST (MultinaryCounterTest, ThreeTurpleTrinaryTest)
  {
  uint max_array[] = {3,3,3};

  vector<uint> max (max_array, max_array+3);
  internal::MultinaryCounter counter (max);

  uint ans[][3] = {
    {0,0,0},
    {0,0,1},
    {0,0,2},
    {0,1,0},
    {0,1,1},
    {0,1,2},
    {0,2,0},
    {0,2,1},
    {0,2,2},
    {1,0,0},
    {1,0,1},
    {1,0,2},
    {1,1,0},
    {1,1,1},
    {1,1,2},
    {1,2,0},
    {1,2,1},
    {1,2,2},
    {2,0,0},
    {2,0,1},
    {2,0,2},
    {2,1,0},
    {2,1,1},
    {2,1,2},
    {2,2,0},
    {2,2,1},
    {2,2,2}
    };
  uint num_seq = 27;

  for (uint i=0;; i++)
    {
    vector<uint> actual (3, 0);

    actual[0] = counter.at (0);
    actual[1] = counter.at (1);
    actual[2] = counter.at (2);

    EXPECT_TRUE (VectorIsEqual (actual, ans[i])) << "error occurs at i = " << i;
  
    if (i == num_seq-1)
      {
      break;
      }

    EXPECT_TRUE (counter++);
    } 

  for (uint i=num_seq; i<num_seq+10; i++)
    {
    EXPECT_FALSE (counter++);

    vector<uint> actual (3, 0);
    actual[0] = counter.at (0);
    actual[1] = counter.at (1);
    actual[2] = counter.at (2);

    EXPECT_TRUE (VectorIsEqual (actual, ans[num_seq-1])) << "error occurs at i = " << i;    
    }
  }

TEST (MultinaryCounterTest, TwoFourThreeNaryTest)
  {
  uint max_array[] = {2,4,3};
  vector<uint> max (max_array, max_array+3);
  internal::MultinaryCounter counter (max);

  uint ans[][3] = {
    {0,0,0},
    {0,0,1},
    {0,0,2},
    {0,1,0},
    {0,1,1},
    {0,1,2},
    {0,2,0},
    {0,2,1},
    {0,2,2},
    {0,3,0},
    {0,3,1},
    {0,3,2},
    {1,0,0},
    {1,0,1},
    {1,0,2},
    {1,1,0},
    {1,1,1},
    {1,1,2},
    {1,2,0},
    {1,2,1},
    {1,2,2},
    {1,3,0},
    {1,3,1},
    {1,3,2}
    };
  uint num_seq = 24;

  for (uint i=0;; i++)
    {
    vector<uint> actual (3, 0);

    actual[0] = counter.at (0);
    actual[1] = counter.at (1);
    actual[2] = counter.at (2);

    EXPECT_TRUE (VectorIsEqual (actual, ans[i])) << "error occurs at i = " << i;
  
    if (i == num_seq-1)
      {
      break;
      }

    EXPECT_TRUE (counter++);
    } 

  for (uint i=num_seq; i<num_seq+10; i++)
    {
    EXPECT_FALSE (counter++);

    vector<uint> actual (3, 0);
    actual[0] = counter.at (0);
    actual[1] = counter.at (1);
    actual[2] = counter.at (2);

    EXPECT_TRUE (VectorIsEqual (actual, ans[num_seq-1])) << "error occurs at i = " << i;    
    }

  }

TEST (ReconnectionPatternCounter_odd_kTEST, k3n6Test)
  {
  uint test_vector[][3] = {
    // Graph-0
    // {from, to_old, to_new} pattern index 0
    {2,0,4},
    {2,1,5},
    // {from, to_old, to_new} pattern index 1
    {2,0,4},
    {3,1,5},
    // {from, to_old, to_new} pattern index 2
    {3,0,4},
    {2,1,5},
    // {from, to_old, to_new} pattern index 3
    {3,0,4},
    {3,1,5},
    // {from, to_old, to_new} pattern index 4
    {2,0,5},
    {2,1,4},
    // {from, to_old, to_new} pattern index 5
    {2,0,5},
    {3,1,4},
    // {from, to_old, to_new} pattern index 6
    {3,0,5},
    {2,1,4},
    // {from, to_old, to_new} pattern index 7
    {3,0,5},
    {3,1,4},

    // Graph-1
    // {from, to_old, to_new} pattern index 0
    {1,0,4},
    {1,2,5},
    // {from, to_old, to_new} pattern index 1
    {1,0,4},
    {3,2,5},
    // {from, to_old, to_new} pattern index 2
    {3,0,4},
    {1,2,5},
    // {from, to_old, to_new} pattern index 3
    {3,0,4},
    {3,2,5},
    // {from, to_old, to_new} pattern index 4
    {1,0,5},
    {1,2,4},
    // {from, to_old, to_new} pattern index 5
    {1,0,5},
    {3,2,4},
    // {from, to_old, to_new} pattern index 6
    {3,0,5},
    {1,2,4},
    // {from, to_old, to_new} pattern index 7
    {3,0,5},
    {3,2,4},

    // Graph-2
    // {from, to_old, to_new} pattern index 0
    {1,0,4},
    {1,3,5},
    // {from, to_old, to_new} pattern index 1
    {1,0,4},
    {2,3,5},
    // {from, to_old, to_new} pattern index 2
    {2,0,4},
    {1,3,5},
    // {from, to_old, to_new} pattern index 3
    {2,0,4},
    {2,3,5},
    // {from, to_old, to_new} pattern index 4
    {1,0,5},
    {1,3,4},
    // {from, to_old, to_new} pattern index 5
    {1,0,5},
    {2,3,4},
    // {from, to_old, to_new} pattern index 6
    {2,0,5},
    {1,3,4},
    // {from, to_old, to_new} pattern index 7
    {2,0,5},
    {2,3,4},

    // Graph-3
    // {from, to_old, to_new} pattern index 0
    {0,1,4},
    {0,2,5},
    // {from, to_old, to_new} pattern index 1
    {0,1,4},
    {3,2,5},
    // {from, to_old, to_new} pattern index 2
    {3,1,4},
    {0,2,5},
    // {from, to_old, to_new} pattern index 3
    {3,1,4},
    {3,2,5},
    // {from, to_old, to_new} pattern index 4
    {0,1,5},
    {0,2,4},
    // {from, to_old, to_new} pattern index 5
    {0,1,5},
    {3,2,4},
    // {from, to_old, to_new} pattern index 6
    {3,1,5},
    {0,2,4},
    // {from, to_old, to_new} pattern index 7
    {3,1,5},
    {3,2,4},

    // Graph-4
    // {from, to_old, to_new} pattern index 0
    {0,1,4},
    {0,3,5},
    // {from, to_old, to_new} pattern index 1
    {0,1,4},
    {2,3,5},
    // {from, to_old, to_new} pattern index 2
    {2,1,4},
    {0,3,5},
    // {from, to_old, to_new} pattern index 3
    {2,1,4},
    {2,3,5},
    // {from, to_old, to_new} pattern index 4
    {0,1,5},
    {0,3,4},
    // {from, to_old, to_new} pattern index 5
    {0,1,5},
    {2,3,4},
    // {from, to_old, to_new} pattern index 6
    {2,1,5},
    {0,3,4},
    // {from, to_old, to_new} pattern index 7
    {2,1,5},
    {2,3,4},

    // Graph-5
    // {from, to_old, to_new} pattern index 0
    {0,2,4},
    {0,3,5},
    // {from, to_old, to_new} pattern index 1
    {0,2,4},
    {1,3,5},
    // {from, to_old, to_new} pattern index 2
    {1,2,4},
    {0,3,5},
    // {from, to_old, to_new} pattern index 3
    {1,2,4},
    {1,3,5},
    // {from, to_old, to_new} pattern index 4
    {0,2,5},
    {0,3,4},
    // {from, to_old, to_new} pattern index 5
    {0,2,5},
    {1,3,4},
    // {from, to_old, to_new} pattern index 6
    {1,2,5},
    {0,3,4},
    // {from, to_old, to_new} pattern index 7
    {1,2,5},
    {1,3,4}};
  uint test_vector_len = sizeof (test_vector) / sizeof (uint) / 3;

  uint k = 3;

  Graph g = CreateCompleteGraph (k+1);
  list<Graph> all_grown_g = GrowGraph_k3 (g);

  uint test_vector_index = 0;
  uint g_index = 0;
  foreach (const Graph& g, all_grown_g)
    {
    ReconnectionPatternCounter_odd_k reconnectionCounter (g);
    do
      {
      do
        {
        vector<uint> reconnect = reconnectionCounter.GetEdgeToReconnect ();
        EXPECT_TRUE (VectorIsEqual (reconnect, test_vector[test_vector_index]));
        test_vector_index++;
        }
        while (reconnectionCounter.NextEdgeToReconnect ());
      }
      while (reconnectionCounter.NextReconnectionPattern ());
    }
  }

TEST (ReconnectionPatternCounter_odd_kTEST, DISABLED_k3n6rintTestVector)
  {
  uint k = 3;

  Graph g = CreateCompleteGraph (k+1);
  list<Graph> grown_g = GrowGraph_k3 (g);

  uint g_index = 0;
  foreach (Graph& g, grown_g)
    {
    DEBUG_PRINT_GRAPH ("k" << k << "-grow1-ver" << g_index, g);

    ReconnectionPatternCounter_odd_k reconnectionCounter (g);
    cout << "// Graph-" << g_index++ << endl;
    do
      {
      cout << "// {from, to_old, to_new} pattern index " << reconnectionCounter.GetIndex () << endl;
      do
        {
        vector<uint> reconnect = reconnectionCounter.GetEdgeToReconnect ();
        cout 
          << tuples::set_delimiter (',') << tuples::set_open ('{') << tuples::set_close ('}')
          << tie (reconnect[0], reconnect[1], reconnect[2]) << "," << endl;
        }
        while (reconnectionCounter.NextEdgeToReconnect ());
      }
      while (reconnectionCounter.NextReconnectionPattern ());
      cout << endl;
    }
  }